/**
 * @file maze_recursive_division.js, an implementation for maze.js to generate a maze by recursive division method.
 *
 * @author nobu <nobu@ctmk.amanek.jp>
 */

(function(define) {
define([], function() {
	/**
	* @constructor
	*/
	var Maze_Algorithm = function() {
		// initialize
	};
	
	/**
	 * Generate a maze.
	 *
	 * @return {Maze.Result}
	 * @param {Maze.Config} config
	 * @param {number] [config.width_divisible] - specify smallest width of area divisible.
	 * @param {number] [config.height_divisible] - specify smallest height of area divisible.
	 * @throw {RangeError} It will throw if any config option is invalid.
	 */
	Maze_Algorithm.generate = function (config) {
		return generate_by_recursive_division(config);
	};
	
	/**
	 * Signature of this method.
	 */
	Maze_Algorithm.Signature = function() {
		return "recursive-division";
	};

	return Maze_Algorithm;

	/**
	 * @class
	 */
	function Work(config) {
		if (config.need_process) {
			this.process = [];
		}
		this.data = [];
	}
	
	/**
	 * Generate a maze by recursive division method.
	 * @return {Maze.Result}
	 * @param {Maze.Config} config
	 */
	function generate_by_recursive_division(config) {
		validate(config);
		work = new Work(config);

		work.data = Maze_Algorithm.get_data_filled_with_edges(config.width, config.height, Maze_Algorithm.CellType.PATH, Maze_Algorithm.CellType.WALL);
		if (config.need_process) {
			work.process = Maze_Algorithm.get_process_filling_edges(config.width, config.height, Maze_Algorithm.CellType.WALL);
		}

		var width_divisible = config.width_divisible || 3;
		var height_divisible = config.height_divisible || 3;
		divide_areas(work, config.width, config.height, width_divisible, height_divisible);
		
		result = new Maze_Algorithm.Result(config, Maze_Algorithm.Signature());
		if (config.need_data) {
			result.data = work.data;
		}
		if (config.need_process) {
			result.process = work.process;
			result.celltype_to_fill = Maze_Algorithm.CellType.PATH;
		}
		return result;
	}
	
	/**
	 * @param {Maze.Config} config
	 */
	function validate(config) {
		// limitations in this algorithm.
		if ((config.width < 3) || (config.width%2 === 0) || (config.height < 3) || (config.height%2 === 0)) {
			throw new RangeError("config.width and config.height must be at least 3 and be a odd number.");
		}
		if ((typeof config.width_divisible !== 'undefined' && config.width_divisible < 3) || (typeof config.height_divisible !== 'undefined' && config.height_divisible < 3)) {
			throw new RangeError("config.width_divisible and config.height_divisible must be at least 3.");
		} 
	}

	/**
	 * @param {Maze_Algorithm.Work} work
	 * @param {number} x
	 * @param {number} y
	 * @param {number} width
	 * @param {number} height
	 * @param {number} width_divisible
	 * @param {number} height_divisible
	 */
	function divide_areas(work, width, height, width_divisible, height_divisible) {
		var put_wall = ('process' in work) ? function (work, x, y) { return Maze_Algorithm.put_with_process(work, x, y, Maze_Algorithm.CellType.WALL); } : function (work, x, y) { return Maze_Algorithm.put_without_process(work, x, y, Maze_Algorithm.CellType.WALL); };
		var put_path = ('process' in work) ? function (work, x, y) { return Maze_Algorithm.put_with_process(work, x, y, Maze_Algorithm.CellType.PATH); } : function (work, x, y) { return Maze_Algorithm.put_without_process(work, x, y, Maze_Algorithm.CellType.PATH); };

		work.divisions = [];
		work.divisions.push({ x: 1, y: 1, width: width-2, height: height-2});	// ignore outer walls.

		while (work.divisions.length > 0) {
			var division = work.divisions.shift();
			if (division.width < width_divisible || division.height < height_divisible) {
				continue;
			}

			// dividing position
			var h = Math.floor(Math.random()*(division.width>>1)) * 2 + 1;
			var v = Math.floor(Math.random()*(division.height>>1)) * 2 + 1;

			put_separation_walls(work, division.x, division.y, division.width, division.height, h, v, put_wall);
			make_holes_to_separation_walls(work, division.x, division.y, division.width, division.height, h, v, put_path);

			// push sub-divisions
			work.divisions.push({ x: division.x, y: division.y, width: h, height: v });
			work.divisions.push({ x: division.x+h+1, y: division.y, width: division.width-(h+1), height: v });
			work.divisions.push({ x: division.x, y: division.y+v+1, width: h, height: division.height-(v+1) });
			work.divisions.push({ x: division.x+h+1, y: division.y+v+1, width: division.width-(h+1), height: division.height-(v+1) });
		}
	}
	
	/**
	 * @param {Maze_Algorithm.Work} work
	 * @param {number} x
	 * @param {number} y
	 * @param {number} width
	 * @param {number} height
	 * @param {number} h
	 * @param {number} v
	 * @param {function} put_wall - way to put a wall.
	 */
	function put_separation_walls(work, x, y, width, height, h, v, put_wall) {
		var hh = x + h;
		var vv = y + v;
		for (var xx = 0; xx < width; xx += 1) {
			put_wall(work, x+xx, vv);
		}
		for (var yy = 0; yy < height; yy += 1) {
			put_wall(work, hh, y+yy);
		}
	}
	
	/**
	 * @param {Maze_Algorithm.Work} work
	 * @param {number} x
	 * @param {number} y
	 * @param {number} width
	 * @param {number} height
	 * @param {number} h
	 * @param {number} v
	 * @param {function} put_wall - way to put a path.
	 */
	function make_holes_to_separation_walls(work, x, y, width, height, h, v, put_path) {
		// candidates to remove
		var removables = [
			{ x: x+h, y: y + (Math.floor(Math.random()*(v>>1))<<1) },
			{ x: x+h, y: y + v+1 + (Math.floor(Math.random()*((height-(v+1))>>1))<<1) },
			{ x: x + (Math.floor(Math.random()*(h>>1))<<1), y: y+v },
			{ x: x + h+1 + (Math.floor(Math.random()*((width-(h+1))>>1))<<1), y: y+v }
		];
		// choise not to remove
		var not_to_remove = 0x1 << Math.floor(Math.random()*removables.length);
		// remove walls
		for (var i = 0; i < removables.length; i += 1) {
			if ((0x1 << i) & not_to_remove) {
				continue;
			}
			put_path(work, removables[i].x, removables[i].y);
		}
	}

});
})(typeof define !== 'undefined' ?
	// Use define for AMD if available
	define :
	// If no define, look for module to export as a CommonJS module.
	typeof module !== 'undefined' ?
	function(deps, factory) { module.exports = factory(); } :
	// If no define or module, attach to current context.
	typeof Maze !== 'undefined' ?
	function(deps, factory) { this.Maze.RecursiveDivision = factory(); } :
	function(deps, factory) { this.Maze_RecursiveDivision = factory(); }
);
